#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<string>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void dfs(TreeNode* root, string& str)
{
    if (!root)   str += "None,";
    else
    {
        str += to_string(root->val) + ",";
        dfs(root->left, str);
        dfs(root->right, str);
    }
}
string serialize(TreeNode* root) {
    string res;
    dfs(root, res);
    return res;
}

TreeNode* read(list<string>& a)
{
    if (a.front() == "None")
    {
        a.pop_front();
        return nullptr;
    }

    auto root = new TreeNode(stoi(a.front()));
    a.pop_front();
    root->left = read(a);
    root->right = read(a);

    return root;
}

TreeNode* deserialize(string data) {
    list<string> a;
    string s;
    for (auto c : data)
    {
        if (c == ',')
        {
            a.push_back(s);
            s.clear();
        }
        else s += c;
    }
    if (!s.empty())  a.push_back(s);

    return read(a);
}